package recursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/3/6
 * @verdion 1.0.0
 * A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
 *
 * Find all strobogrammatic numbers that are of length = n.
 *
 * Example:
 *
 * Input:  n = 2
 * Output: ["11","69","88","96"]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/strobogrammatic-number-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FindStrobogrammatic {
    public List<String> findStrobogrammatic(int n) {
        return find(1,n);
    }

    private List<String> find(int start, int end){
        List<String> list = new ArrayList<>();
        if(start > end){
            return list;
        }
        if(start == end){
            list.add("0");
            list.add("1");
            list.add("8");
            return list;
        }
        if(start != 1){
            list.addAll(Arrays.asList("00", "11", "69","88","96"));
        } else {
            list.addAll(Arrays.asList("11", "69","88","96"));
        }

        List<String> res = new ArrayList<>();
        List<String> childs = find(start + 1, end -1);
        if(childs.size() != 0){

            for(String str: list){
                for(String c: childs){
                    StringBuilder builder = new StringBuilder(str);
                    builder.insert(1, c);
                    res.add(builder.toString());
                }
            }
        } else {
            return list;
        }
        return res;
    }
}
